/**
 * 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
 */
public class Test1277 {

    public static void main(String[] args) {
        int[][] squares = {{1,0,1},{1,1,0},{1,1,0}};
        countSquares(squares);
    }

    public static int countSquares(int[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        int count = 0;

        for (int i = 0; i < matrix.length; i++) {
            count += matrix[i][0];
            dp[i][0] = matrix[i][0];
        }
        for (int i = 1; i < matrix[0].length; i++) {
            count += matrix[0][i];
            dp[0][i] = matrix[0][i];
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 1){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                    count += dp[i][j];
                }
            }
        }
        return count;
    }
}
